import java.util.PriorityQueue;

public class MedianFinder {
    // leetcode 数据流的中位数
    // https://leetcode.cn/problems/find-median-from-data-stream/description/?envType=study-plan-v2&envId=top-100-liked
    // 维护两个优先级队列，小于等于中位数的优先级队列queMin和大于中位数的队列queMax
    // 并且为了方便求出中位数需要保证queMin是大根堆，queMax是小根堆
    PriorityQueue<Integer> queMin, queMax;

    public MedianFinder() {
        queMin = new PriorityQueue<>((a,b) -> {
            return b-a;
        });
        queMax = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (queMin.isEmpty() || num < queMin.peek()) {
            queMin.offer(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.offer(queMin.poll());
            }
        }else {
            queMax.offer(num);
            if (queMax.size() > queMin.size()) {
                queMin.offer(queMax.poll());
            }
        }
    }

    public double findMedian() {
        if ((queMin.size() + queMax.size()) % 2 == 1) {
            return queMin.peek();
        }else {
            return (queMax.peek() + queMin.peek()) / 2.0;
        }
    }
}
